/*
https://leetcode.cn/problems/house-robber-ii/submissions/562235065/
力扣213.打家劫舍II
*/
class Solution {
    int dp[101][2];
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1){
            return nums[0];
        }else if(n==2) return max(nums[0],nums[1]);
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<n;++i){
            for(int j=0;j<2;++j){
                if(i==1){
                    if(j==0) dp[1][0]=nums[1];
                    else dp[1][1]=nums[0];
                }else if(i==n-1&&j==1) dp[i][j]=dp[i-1][j];
                else dp[i][j]=max(dp[i-1][j],dp[i-2][j]+nums[i]);

            }
        }
        return max(dp[n-1][0],dp[n-1][1]);
    }
};